\subsection{An $O(\min\{n\sqrt{k\log n}, nk\})$ round algorithm}
\label{sec:upper}
Our algorithm is given in Algorithm~\ref{alg:flow_based} and analyzed
in Lemma~\ref{lem:level.flow} and Theorem~\ref{thm:flow_based}.

\begin{algorithm}[ht!]
\caption{$O(\min\{n \sqrt{k\log n}, nk\})$ round algorithm in the
  offline model}
\label{alg:flow_based}
\begin{algorithmic}[1]
  \REQUIRE A sequence of communication graphs $G_i$, $i = 1, 2, \ldots$
  \ENSURE Schedule to disseminate $k$ tokens.

  \medskip

  \IF{$k \leq \sqrt{\log n}$}

  \FOR{each token $t$} \label{alg.step:flow_based.trivial}

  \STATE For the next $n$ rounds, let every node that has token
  $t$ broadcast the token.

  \ENDFOR 

  \ELSE

  \STATE Choose a set $S$ of $2\sqrt{k \log n}$ random nodes. \label{alg.step:random}
  
  \FOR{each vertex in $v \in S$} \label{alg.step:flow_based.phase_1}

  \STATE Send each of the $k$ tokens to vertex $v$ in $O(n)$ rounds. 

  \ENDFOR

  \FOR{each token $t$} \label{alg.step:flow_based.phase_2}

  \STATE For the next $2n \sqrt{(\log n)/k}$ rounds, let every node with token
  $t$ broadcast it.

  \ENDFOR

  \ENDIF

\end{algorithmic}
\end{algorithm}

%\vspace{-1cm}

\begin{lemma}
\label{lem:level.flow}
Let $k \leq n$ tokens be at given source nodes and $v$ be an arbitrary
node. Then, all the tokens can be sent to $v$ using broadcasts in
$O(n)$ rounds.
\end{lemma}

\begin{theorem}
\label{thm:flow_based}
Algorithm~\ref{alg:flow_based} solves the $k$-gossip problem using
$O(\min\{n \sqrt{k \log n}, nk\})$ rounds with high probability in
the offline model.
\end{theorem}

Algorithm~\ref{alg:flow_based} can be derandomized using the technique
of conditional expectations, as shown in
Algorithm~\ref{alg:derandomize} in Appendix~\ref{app:upper} and
analyzed in Lemma~\ref{lem:derandomize}.
